Directed graphs, weights, shortest paths, APSP

In [18]:

    

%matplotlib inline
import networkx as nx
import matplotlib.pyplot as plt


G = nx.DiGraph()

#add some edges with weights
G.add_edge(1,2, weight=15)
G.add_edge(1,3,weight=1)
G.add_edge(1,4,weight=2)
G.add_edge(1,6,weight=18)
G.add_edge(2,4,weight=1)
G.add_edge(2,5,weight=3)
G.add_edge(2,6,weight=2)
G.add_edge(3,5,weight=8)
G.add_edge(3,6,weight=1)
G.add_edge(4,5,weight=2)
G.add_edge(5,4,weight=3)
G.add_edge(5,6,weight=3)
G.add_edge(6,7,weight=1)
G.add_edge(7,2,weight=1)

#visualize this graph
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G,pos,node_size=700,node_color='b')
nx.draw_networkx_labels(G, pos, font_size=20)
nx.draw_networkx_edges(G,pos,edge_color='r',arrow=True)


plt.axis('off')
plt.savefig("weighted_digraph.png") # save as png
plt.show() # display


    

In [19]:

    

nx.dijkstra_path(G,1,5,weight='weight')


    

    
Out[19]:





[1, 4, 5]

In [21]:

    

nx.dijkstra_path(G,1,7,weight='weight')


    

    
Out[21]:





[1, 3, 6, 7]

In [22]:

    

nx.single_source_dijkstra_path(G,1,weight='weight')


    

    
Out[22]:





{1: [1],
 2: [1, 3, 6, 7, 2],
 3: [1, 3],
 4: [1, 4],
 5: [1, 4, 5],
 6: [1, 3, 6],
 7: [1, 3, 6, 7]}

In [25]:

    

nx.all_pairs_dijkstra_path(G,weight='weight')


    

    
Out[25]:





{1: {1: [1],
  2: [1, 3, 6, 7, 2],
  3: [1, 3],
  4: [1, 4],
  5: [1, 4, 5],
  6: [1, 3, 6],
  7: [1, 3, 6, 7]},
 2: {2: [2], 4: [2, 4], 5: [2, 5], 6: [2, 6], 7: [2, 6, 7]},
 3: {2: [3, 6, 7, 2],
  3: [3],
  4: [3, 6, 7, 2, 4],
  5: [3, 6, 7, 2, 5],
  6: [3, 6],
  7: [3, 6, 7]},
 4: {2: [4, 5, 6, 7, 2], 4: [4], 5: [4, 5], 6: [4, 5, 6], 7: [4, 5, 6, 7]},
 5: {2: [5, 6, 7, 2], 4: [5, 4], 5: [5], 6: [5, 6], 7: [5, 6, 7]},
 6: {2: [6, 7, 2], 4: [6, 7, 2, 4], 5: [6, 7, 2, 5], 6: [6], 7: [6, 7]},
 7: {2: [7, 2], 4: [7, 2, 4], 5: [7, 2, 5], 6: [7, 2, 6], 7: [7]}}

In [26]:

    

nx.floyd_warshall(G,weight='weight')


    

    
Out[26]:





{1: defaultdict(<function networkx.algorithms.shortest_paths.dense.<lambda>>,
             {1: 0, 2: 4, 3: 1, 4: 2, 5: 4, 6: 2, 7: 3}),
 2: defaultdict(<function networkx.algorithms.shortest_paths.dense.<lambda>>,
             {1: inf, 2: 0, 3: inf, 4: 1, 5: 3, 6: 2, 7: 3}),
 3: defaultdict(<function networkx.algorithms.shortest_paths.dense.<lambda>>,
             {1: inf, 2: 3, 3: 0, 4: 4, 5: 6, 6: 1, 7: 2}),
 4: defaultdict(<function networkx.algorithms.shortest_paths.dense.<lambda>>,
             {1: inf, 2: 7, 3: inf, 4: 0, 5: 2, 6: 5, 7: 6}),
 5: defaultdict(<function networkx.algorithms.shortest_paths.dense.<lambda>>,
             {1: inf, 2: 5, 3: inf, 4: 3, 5: 0, 6: 3, 7: 4}),
 6: defaultdict(<function networkx.algorithms.shortest_paths.dense.<lambda>>,
             {1: inf, 2: 2, 3: inf, 4: 3, 5: 5, 6: 0, 7: 1}),
 7: defaultdict(<function networkx.algorithms.shortest_paths.dense.<lambda>>,
             {1: inf, 2: 1, 3: inf, 4: 2, 5: 4, 6: 3, 7: 0})}

In [27]:

    

nx.bellman_ford(G,1,weight='weight')


    

    
Out[27]:





({1: None, 2: 7, 3: 1, 4: 1, 5: 4, 6: 3, 7: 6},
 {1: 0, 2: 4, 3: 1, 4: 2, 5: 4, 6: 2, 7: 3})

In [67]:

    

nx.betweenness_centrality(G,k=None,weight='weight')


    

    
Out[67]:





{1: 0.0,
 2: 0.23333333333333334,
 3: 0.1,
 4: 0.1,
 5: 0.1,
 6: 0.36666666666666664,
 7: 0.3}